#include <iostream>
#include <conio.h>
using namespace std;

static string ranks[13] = { "2", "3", "4", "5", "6", "7", "8", "9", "10", "Knight", "Queen", "King", "Ace"};
static string suits[4] = { "Hearts", "Spades", "Diamonds", "Clubs"};

class Card {
    public:
    int value, suit;

    Card(int value_, int suit_){
        value = value_; suit = suit_;
    }

    Card(){
    }

    string toString(){
        string info = ranks[value];
        info.append(" of ");
        info.append(suits[suit]);

        return info;
    }
};

class Deck {
    private:
    Card* theCards[52];
    int iterator;

    public:
    Deck(){
        int counter = 0;
        for(int i=0; i<4; i++)
            for(int j=0; j<13; j++){
                theCards[counter++] = new Card(j,i);
            }
        iterator=51;

    }

    Card *getCard(){
        return theCards[iterator--];
    }

    int getNoOfCards(){
        return iterator;
    }

    void shuffle(){
        Card* tempCard;
        int spotA, spotB;
        for(int i= 0; i<1000; i++){
            spotA = rand()%52;
            spotB = rand()%52;
            tempCard = theCards[spotA];
            theCards[spotA] = theCards[spotB];
            theCards[spotB] = tempCard;
        }
    }

    void reset(){
        iterator = 51;
    }

};

struct cardElement{
  Card *card;
  struct cardElement *next;
};

class LinkedList{

    private:
        cardElement *start;

    public:
    LinkedList(){
        start = NULL;
    }

    bool isEmpty(){
        return (start==NULL);
    }

    void push(Card *c){
        cardElement *newElement;
        newElement=(cardElement *)malloc(sizeof(cardElement));
        newElement->card = c;
        newElement->next = start;
        start=newElement;
    }

    int getSize(){
        cardElement *p = start;
        int size = 0;

        if(start!=NULL){
            size++;
            while(p->next!=NULL){
                p = p->next;
                size++;}
        }
        return size;
    }

    Card* pop(){
        Card* c = start->card;
        cardElement *p = start;
        start = start->next;
        free(p);
        return c;
    }

    Card* getTopCard(){
        if(start!=NULL){
            Card* c = start->card;
            return c;}

        return NULL;
    }


    void showTopCard(){
        if(start!=NULL){
            Card* c = start->card;
            cout << (*c).toString();
        }
        else{
            cout << "(empty)";
        }
    }
};

void drawNewCards(Deck* deck, LinkedList pile[]){
    for(int i=0; i<4; i++)
        pile[i].push((*deck).getCard());
}

int checkIfSameSuit(LinkedList pile[]){
    int suits[4] = { 0 }, maxSuit = -1;
    Card* c;
    for(int i=0; i<4; i++){
        c = pile[i].getTopCard();
        if(c!=NULL)
            suits[(*c).suit]++;}

    for(int i=0; i<4; i++)
        if(suits[i]>1) maxSuit = i;
    return maxSuit;
}

void removeSameColor(LinkedList pile[]){
    int suitToRemove, minValue = 15, minSpot = -1;

    do{
        suitToRemove = checkIfSameSuit(pile);
        if(suitToRemove==-1) return; //No card can be removed

        for(int i=0; i<4; i++){
            Card* c = pile[i].getTopCard();
            if(c != NULL)
                if((*c).suit == suitToRemove && (*c).value < minValue){
                    minSpot = i; minValue = (*c).value;}
        }
        pile[minSpot].pop();
        minValue = 15; minSpot = -1;
    }while(true);
}

void moveToEmpty(LinkedList pile[], int counter){
    int emptyPile = -1, noOfEmptyPiles =0, highestValuePile = -1, highestValue = -1;

    for(int i=0; i<4; i++){
        if(pile[i].getSize() == 0){ //Check for empty pile
            emptyPile = i;
            noOfEmptyPiles++;
            }
        else{
            Card* c = pile[i].getTopCard();
            if((*c).value > highestValue){ //Check which one has the highest value
                highestValuePile = i; highestValue = (*c).value;}
        }
    }

    if(emptyPile>-1){
        Card* c = pile[highestValuePile].pop();
        pile[emptyPile].push(c);
        if(counter>1 && noOfEmptyPiles > 1)
            moveToEmpty(pile, counter-1);  //At the most 3 cards can be moved
    }

    return;
}


int main(string args[]){
    srand(time(NULL));

    LinkedList pile[4];
    Deck* deck = new Deck();
    srand(time(NULL));

    int cardsLeft, leftOvers, totalLeft = 0, completed = 0;


    #define ATTEMPTS    100000
    cout << "Doing " << ATTEMPTS << " loops..";
    for(int j = 0; j<ATTEMPTS ; j++){
        (*deck).shuffle();
        do{
            drawNewCards(deck, pile);

            do{
            removeSameColor(pile);
            moveToEmpty(pile, 3);
            } while(checkIfSameSuit(pile) > -1);

            cardsLeft = (*deck).getNoOfCards();

        } while(cardsLeft > 0);

        leftOvers = 0;
        for(int i =0; i<4; i++)
            leftOvers += pile[i].getSize();

        if(leftOvers < 5){
            completed++;
        }

        totalLeft += leftOvers;

        //Empty stacks
        for(int i =0; i<4; i++)
            while(!pile[i].isEmpty())
                pile[i].pop();

        //Reset deck
        (*deck).reset();
        if(j%10000 == 0) cout << ".";
    }

    cout << "\n\nAverage amount of cards left: " << (float) totalLeft/ATTEMPTS << endl;

    cout << "Out of " << ATTEMPTS << " attempts " << completed << " were completed." << endl;



    cout << endl << endl;
    delete deck;
    return (EXIT_SUCCESS);
}

